#include <vector>
#include <unordered_map>
using namespace std;
class Solution
{
public:
    // 当数组元素全都是正数的时候，可以使用滑动窗口
    // 但是如果不全为正数，就不行
    //  int subarraySum(vector<int>& nums, int k) {
    //      //如何找到和为k的子数组呢？
    //      //利用一个额外数组可以做到吗？
    //      int sum = 0, ans = 0;
    //      for(int left = 0, right = 0; right < nums.size(); ++right)
    //      {
    //          sum += nums[right];
    //          while(sum > k) sum -= nums[left++];
    //          if(sum == k) ans++;
    //      }
    //      return ans;
    //  }
    int subarraySum(vector<int> &nums, int k)
    {
        // 利用前缀和和哈希表可以完成任务
        // 哈希表是为了快速查找
        // 哈希表保存的是每个前缀和的个数
        unordered_map<int, int> hash;
        int sum = 0, ans = 0;
        hash[0] = 1;
        for (auto e : nums)
        {
            sum += e;
            if (hash.count(sum - k))
                ans += hash[sum - k];
            hash[sum]++;
            // 每次插入的时候就进行查找就能保证不会查找到后面的
        }
        return ans;
    }
};